1. Field of the Invention
The present invention generally relates to routing equipment, and more particularly to a router that has a function to prevent a packet sequence inversion with the use of a plurality of processing engines connected in parallel.
Generally, the routing equipment is required to perform address/flow determination processing that determines the destination address for the incoming packets and the output port specified for the outgoing packets. Moreover, the routing equipment is required to provide the quality assurance services that guarantee the communication quality factors such as the low delivery delay, the bandwidth requirement, the transmission requirement, the jitter requirement and so on. If the speed of a network becomes high, it is difficult for a single processing unit to process the above-mentioned functions of the destination-address/flow determination and the quality assurance services at high speed. Hence, using a plurality of processing units that are connected in parallel and perform the above functions in a distributed manner is currently demanded.
2. Description of the Related Art
FIG. 11 shows a carrier/provider network in which a conventional router is provided.
In the network in FIG. 11, edge routers 101, core routers 102, and user sites 106 are provided. In the present case, six user sites or user networks, indicated by “USER SITE1” through “USER SITE6”, are provided. The routers, currently used with the career/provider network, are usually equipped with the functions to determine the destination address of packets, which are received from or transmitted to each user network, and provide the quality assurance services for such packets. Thus, for example, the USER SITE1 and the USER SITE6 can exchanges the data that are transmitted over the network.
In recent years, with rapid spreading of the Internet and speed improvement of the network, it is becoming impossible for a single processing unit to perform the functions of the destination-address/flow determination and the quality assurance services for all the packets that are received. Hence, a router using a plurality of processing units that are connected in parallel and perform the above functions in a distributed manner is currently demanded.
FIG. 12 shows a conventional router which uses a plurality of distributed processing engines.
As shown in FIG. 12, the conventional router 300 uses a plurality of distributed processing engines 308, in order to perform high-speed processing. In the router 300, the incoming packets are input at a receiving interface (RX I/F) 301. A demultiplexer (DMUX) 307 performs the demultiplexing of the incoming packets to the plurality of processing engines 308, and assigns a sequence number to each packet. Each processing engine 308 performs control of the packets in response to the output of the demultiplexer 307. A multiplexer (MUX) 306 performs the frame assembly and waiting control in response to the outputs of the processing engines 308. A transmitting interface (TX I/F) 306 transmits the outgoing packets to the network in response to the output of the multiplexer 309.
As shown in FIG. 12, the processing engine #1 includes a destination-address/flow determination unit (DA/FL DET) 302, a memory 303, a transmitting processing unit (TX PRC) 305, and a scheduling unit 450. In the processing engine #1, the determination unit 302 determines the destination address and the flow of each packet in response to the output of the demultiplexer 307, and stores the packet into the memory 303. The memory 303 is connected to the scheduling unit 450, and the scheduling unit 304 performs the scheduling (quality assurance) of the stored packets based on the header information of each packet. The transmitting processing unit 305 performs transmitting processing of the frames (or packets). The configuration of other processing engines #2 through #4 is the same as the configuration of the processing engine #1 described above.
The demultiplexer 307 performs the demultiplexing of the incoming packets, received at the receiving interface 301, in accordance with the processing performance of each processing engine 308, and performs the distribution of such packets to the plurality of processing engines 308 for every packet. At this time, the demultiplexer 307 assigns a sequence number each packet.
There are two methods of demultiplexing: (1) one packet is divided into various blocks; and (2) the packets are distributed to one of the processing engines for each packet. The sequence number is assigned to each packet in order of the arrival of the incoming packets, and such packets are sent to the plurality of distributed processing engines 308. In each of the processing engines 308, the destination address determination, the flow determination, and the scheduling are performed for each packet, and, thereafter, the processed packets are sent from the processing engines 308 to the multiplexer 309.
The sent-out packets are multiplexed for each packet by using the multiplexer 309. There are two methods of multiplexing that are respectively in conformity with the two methods of demuliplexing. In the case where one packet is divided into various blocks by the demultiplexer 307, the multiplexer 309 performs the waiting and rearranging of the packet blocks for assembling the frame. In the case where the packets are distributed to the processing engines for each packet, the multiplexer 309 performs the waiting of the packets for outputting the packets in order of the sequence number of each packet. The multiplexed packet from the multiplexer 309 is output to the network through the transmitting interface 306.
In the case of the distributed processing engines, it is necessary to perform the sequence number assignment by the demultiplexer 307 and the waiting of the packets by the multiplexer 309. This is because it is expected in an existing IP (Internet Protocol) network that the incoming packets arrive in order of the sequence number of each packet as in the TCP (Transmission Control Protocol). If a packet sequence inversion occurs with some of the incoming packets, the re-transmission of such packets must be performed. In such a case, the amount of useless traffic will be increased.
It should be noted that the above-mentioned distributed processing system has the following problems.
In the case where one packet is divided into various blocks by the demultiplexer 307, only part of the packet is input to each processing engine, and this is not suitable for a processing engine that needs the complete data of one packet for the processing thereof, and the high-speed processing cannot be realized. Moreover, in the case of a multiplexer which needs the high-speed processing corresponding to a high-speed network, the multiplexer must perform the packet assembly that is time consuming, and it cannot respond to the high-speed network.
Moreover, in the case where the packets are distributed to the processing engines for each packet by the demultiplexer 307, the packets that belong to the same flow (the same destination, or the same protocol) are likely to be distributed to different processing engines. It is difficult to efficiently perform the distributed processing of the packets in such a case.
As described above, it is expected in the existing IP network that the incoming packets arrive in order of the sequence number of each packet as in the TCP. If a packet sequence inversion occurs with some of the incoming packets, the re-transmission of such packets must be performed, which will cause the amount of useless traffic to be increased. It is difficult for the conventional router to suitably respond to the above packet sequence inversion.
Moreover, even if the multiplexer on the output side of the router rearranges the outgoing packets in a proper sequence according to the sequence number of each packet, it is difficult to speedily perform the rearrangement of the packets so as to suit the requirements of a high-speed network.